package com.zofer.study.tree;

import java.util.ArrayList;
import java.util.List;

public class KthNode {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(8);
        TreeNode rootl = new TreeNode(6);
        TreeNode rootr = new TreeNode(10);
        TreeNode rootl1 = new TreeNode(5);
        TreeNode rootl2 = new TreeNode(7);
        TreeNode rootr1 = new TreeNode(9);
        TreeNode rootr2 = new TreeNode(11);
        root.left = rootl;
        root.right = rootr;

        rootl.left = rootl1;
        rootl.right = rootl2;

        rootr.left = rootr1;
        rootr.right = rootr2;

        //第k小
        TreeNode treeNode = KthNode(root,1);
        System.out.println("第k小:"+treeNode);
    }

    static TreeNode KthNode(TreeNode pRoot, int k){
        if(pRoot == null || k == 0){
            return null;
        }
        List<String> list = new ArrayList<>();
        midTraverse(pRoot,k,list);
        TreeNode node = null;
        for(int i = 0;i < list.size();i++){
            if(i == k - 1){
                node = new TreeNode(0);
                node.val = Integer.valueOf(list.get(i));
            }
        }
        return node;
    }

    static void midTraverse(TreeNode pRoot,int k,List<String> list)
    {
        if (pRoot == null) {
            return;
        }
        midTraverse(pRoot.left, k, list);
        list.add(String.valueOf(pRoot.val));
        midTraverse(pRoot.right, k, list);

    }
}
